1. Field of the Invention
The present invention generally relates to virtual storage mechanisms for data processing systems and, more particularly, to a dynamic address translation (DAT) mechanism which uses a single translation look aside buffer (TLB) facility for pages of various sizes.
2. Description of the Prior Art
Virtual storage organization and management for data processing systems are described, for example, by Harold S. Stone in High-Performance Computer Architecture, Addison-Wesley (1987), Harvey M. Deitel in An Introduction to Operating Systems, Addison-Wesley (1984), and by Harold Lorin and Harvey M. Deitel in Operating Systems, Addison-Wesley (1981). In a virtual storage system, paging is a relocation and address-to-physical-location binding mechanism providing the user of the system with what appear to be considerably larger memory spaces than are really available. The key feature of the virtual storage concept is disassociating the addresses referenced in a running process from the addresses available in main storage. The addresses referenced by the running process are called virtual addresses, while the addresses available in main storage are called real addresses. The virtual addresses must be mapped into real addresses as the process executes, and that is the function of the dynamic address translation (DAT) mechanism. One such mechanism employs a directory look aside table (DLAT), also known in the art as a translation look-aside buffer (TLB), which stores recent virtual address translations. The terms DLAT and TLB are used interchangeably in the art, but for the sake of consistency, the term TLB is adopted in this application. For virtual addresses stored in the TLB, the translation process requires only a couple of machine cycles. For addresses not stored in the TLB, the process may take on the order of ten to one hundred cycles.
In a system which supports multiple page sizes concurrently, if a fixed set of address bits are used to select a congruence class within a TLB, the logical choice of selection bits would be the low-order bits which distinguish between adjacent pages for the largest allowable page size. However, for small pages, such a choice erodes the locality of reference benefits of congruence classes. Consider, for example, the case of a system with 4 KB and 1 MB pages. If the TLB is two-way set associative with 256 pairs of entries, and if the bits which select a 1 MB page are used to select the congruence class, then all 4 KB pages within a 1 MB (aligned) block are mapped to a single congruence class consisting of only two entries. Therefore, at any instant only 8 KB of any 1 MB block (on a 1 MB boundary) can be "covered" by the TLB when the block is backed by 4 KB pages.
To avoid this problem, set-associative designs for address translation can use a distinct TLB facility for each page size. This is the approach taken in the above-referenced application Ser. No. 07/285,176. Rather than using a fixed field of the address to select a TLB congruence class, address bits used to select a congruence class are chosen as a function of the page size associated with the particular TLB. For each TLB, the address is partitioned into a page number field and a displacement (within a page) field. The low-order bits of the page number field are used as congruence class selection bits. Thus, this approach basically selects a different portion of the address to serve as the TLB congruence selection bits by physically (and statically) routing a distinct combination of address bits to each TLB facility.
As the mix of applications often fluctuates (some parts of the day may tend to be predominantly interactive or commercial, while other times may be characterized by scientific/engineering applications), the optimal balance of large pages and small pages varies. The dual TLB approach with the static routing of congruence class selection bits can not easily adapt. The ability to use any available TLB entry to retain translation information without regard for page size will allow adaptation to workload. Therefore, for a given number of total TLB entries, a single TLB could improve TLB hit rates.
Furthermore, some new architectures may allow a large number of page sizes and, in such systems, a distinct TLB for each page size becomes increasingly impractical with an increase in the number of page sizes. The problem of multiple TLBs (one per page size) is further aggravated by the TLB replication used to enhance performance, as in separate TLBs for scalar and vector units as well as independent DAT facilities among processors. Very little experience exists for multiple page size support. Support for several page sizes would allow software performance experimentation without hardware modification.